#include <bits/stdc++.h>
using namespace std;

// #define ONLINE_JUDGE

#ifndef ONLINE_JUDGE
#define dbg(x...) { cerr << "\033[32;1m" << #x << " -> "; err(x); }
void err() { cerr << "\033[39;0m" << endl; }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif

typedef long long LL;

const int N = 1e5+50;

int s[N][26];

char a[N];

int main(int argc, char const *argv[])
{
	int t;
	scanf("%d", &t);
	for (int kk=1; kk<=t; ++kk)
	{
		int n, q;
		scanf("%d%d", &n, &q);

		memset(s, 0, sizeof(s[0]) * (n+1));
		scanf("%s", a);
		++s[0][a[0]-'A'];
		for (int i=1; i<n; ++i)
		{
			for (int j=0; j<26; ++j)
				s[i][j] += s[i-1][j];
			++s[i][a[i]-'A'];
		}
		int ans = 0;
		for (int _=0; _<q; ++_)
		{
			int l, r; scanf("%d%d", &l, &r);
			--l; --r;
			int cnt = 0;
			for (int i=0; i<26; ++i)
			{
				int x = s[r][i];
				if (l) x -= s[l-1][i];
				if (x & 1) ++cnt;
			}
			ans += cnt <= 1;
		}
		printf("Case #%d: %d\n", kk, ans);
	}
	
	return 0;
}